package com.example.zzy.zzytest.data.structure.recursion;

/**
 * 1.第一个放1行1列
 * 2.第二个放2行1列，判断是否ok，不ok则放第2.3.4...列，找到所有列的合适的位置
 * 3.第三个放3行1.2.3.4...列，直到第八个也得到了合适的位置
 * 4.当找到合适解，开始回溯，即第一个放1行1列的情况下，其余所有皇后在所有列的合适位置均已找到，
 * 这时第一个皇后放第二列，后边继续循环步骤1,2,3,4
 */
public class Queue8 {
    //array[i] == val，第i+1个皇后放在i+1行val+1列，可以看到每个皇后肯定都独占一行，即检查冲突时没必要判断同行
    int[] array = new int[8];
    static int resCount, judgeCount;//解法数量和判断冲突次数

    public static void main(String[] args) {

        Queue8 queue8 = new Queue8();
        queue8.placeAndCheck(0);
        System.out.println("resCount>>>" + resCount + ",judgeCount>>>" + judgeCount);
    }

    //放置一个皇后并检查正确性
    private void placeAndCheck(int no) {
        //已经放完了皇后
        if (no == 8) {
            printChess();
            return;
        }

        //这里循环的是该皇后在该行的列
        for (int i = 0; i < 8; i++) {
            array[no] = i;
            //如果judge通过，再继续放下一个皇后，如果没通过该皇后就继续循环它的列
            if (judge(no)) {
                placeAndCheck(no + 1);
            }
        }
    }

    //找到一种解法，输出结果
    private void printChess() {
        resCount++;
        for (int num : array) {
            System.out.print(num + ",");
        }
        System.out.println();
    }

    //当放置了一个皇后以后，检测它和前面已经放好的皇后是否冲突
    private boolean judge(int no) {
        judgeCount++;
        for (int i = 0; i < no; i++) {
            //没必要判断同行，因为在最初设计时就已经放在不同行
            //判断同列 array[i] == array[no]
            //判断同斜线 等边三角形 Math.abs(no-i) == Math.abs(array[no] - array[i])
            if (array[i] == array[no] || Math.abs(no - i) == Math.abs(array[no] - array[i])) {
                return false;
            }
        }

        return true;
    }


}

